package seqlist.queue.impl;

import seqlist.queue.Queue;

import java.util.NoSuchElementException;

/**
 * 基于整型的循环队列
 */

public class LoopQueue implements Queue<Integer> {
    //定长的数组
    private int[] data;
    //指向队列首元素
    private int head;//这里head 和 tail相当于数组下标，索引。
    //指向队列尾元素
    private int tail;

    //创建有个有参构造方法，根据用户的输入指定数组长度
    public LoopQueue(int size) {
        //因为循环队列要浪费一个空间判断是否已满
        //所以size需要 + 1
        this.data = new int[size + 1];
    }

    @Override// 入队操作
    public void offer(Integer val) {
        if (isFull()) { //如果此时已经满了的话，抛出异常
            throw new ArrayIndexOutOfBoundsException("loopQueue is full,cannot offer");
        }
        data[tail] = val;
        //相同的操作，不能随随便便向后移动，如果是末尾就回到起点
        tail = (tail + 1) % data.length;
    }

    @Override  // 出队操作
    public Integer poll() {
        if(isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll");
        }
        //删除一个元素，相当于对首向后移动一位
        Integer val = data[head];
        //不能随便的移动head，移动引用一定是 + 1 % n
        //因为这是循环队列，上面的条件以及保证数组不为空，
        //所以如果数组走到尾了再向后走一步相当于回到起点。
        head = (head + 1) % data.length;
        return val;
    }

    @Override // 查看队首元素
    public Integer peek() {
        if(isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek");
        }
        return data[head];
    }

    @Override //判断队列是否为空
    public boolean isEmpty() {
        return head == tail;
    }
    //判断是否已满
    public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front[");
        //最后一位元素的下标
        int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
        for(int i = head; i != tail; ){

            sb.append(data[i]);
            if(i != lastIndex){
                sb.append(", ");
            }
            //时刻注意这是个循环队列，不能随意的 + 1
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

}
